package DataStructureAndAlgorithm.LeetCode.DFS;
/*
*输入一个字符串，打印出该字符串中字符的所有排列。
*你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
*
* 输入：s = "abc"
* 输出：["abc","acb","bac","bca","cab","cba"]
*
* 输入：s = "aab"
* 输出：["aba","aab","baa"]
 * */
import java.util.*;
public class ZiFuChuanDePaiLie {
    int res_len = 0;
    List<String> list = new ArrayList<>();
    HashMap<String,Boolean> map = new HashMap<>();
    public String[] permutation(String s) {
        char[] ch = s.toCharArray();
        char[] temp = new char[ch.length];
        boolean[] st = new boolean[ch.length];
        Arrays.fill(st,false);
        for (int i = 0; i < ch.length; i++){
            temp[0] = ch[i];
            Dfs(ch,temp,st,i,0,ch.length);
        }
        String[] res = new String[list.size()];
        int i = 0;
        for (String e : list){
            res[i++] = e;
        }
        Arrays.sort(res);
        return res;
    }
    void Dfs(char[] ch,char[] temp,boolean[] st,int index_ch,int index_temp,int max_len){
        if (index_ch == max_len)return;
        if (index_ch == max_len - 1 && index_temp == ch.length){
            if (!map.containsKey(String.valueOf(temp))){
                list.add(String.valueOf(temp));
                map.put(String.valueOf(temp),true);
            }

        }
        if (st[index_ch] == true)return;
        for (int i = 0; i < max_len; i++){
            temp[index_temp] = ch[index_ch];
            st[index_ch] = true;
            Dfs(ch,temp,st,i,index_temp + 1,max_len);
            st[index_ch] = false;
        }
    }
}
